1. Field of the Invention
The present invention relates to an optimization adjusting method and an optimization adjusting apparatus capable of effectively conducting searches for optimal solutions, by making improvements that compensate for the lack of local solution search abilities which has been considered a drawback inherent in optimization adjusting methods and optimization adjusting apparatus using prior art genetic algorithms for optimal solution estimation problems and the like such as the travelling salesman problem and the circuit design problem.
The invention also relates to an optimization adjusting method and an optimization adjusting apparatus wherein interactive genetic algorithms, by which solution vectors optimum for users can be obtained based on the users' subjective evaluation, are effectively applied to problems where the results of adjustments cannot be evaluated quantitatively since criteria are idealistic and unclear, such as those occurring in the adjustment of the characteristics of hearing aids, the creation of products and interior designs based on inexplicit concepts, and the adjustment of sound and image characteristics to match personal preferences.
2. Description of the Related Art
A genetic algorithm is an optimal solution search method and has the advantage that it rapidly converges to the neighborhood of an optimal solution and does not easily fall into local solutions. Genetic algorithms have been attracting attention particularly in the field of combinatorial optimization. Optimization adjusting methods and optimization adjusting apparatus using genetic algorithms are disclosed in the prior art in such documents as "Genetic Algorithms in Search, Optimization, and Machine Learning" (David E, Goldberg, Addison Wesley), and Japanese Patent Unexamined Publication No. 2-236660. An outline of the prior art will be described below.
FIG. 68 is a flowchart illustrating the principle of optimal solution estimation using a prior art genetic algorithm.
&lt;&lt;Step 1&gt;&gt;
Consider a set P consisting of n members, each member being an m-dimensional vector p.sub.k (p.sub.k1, p.sub.k2, . . . , p.sub.km). Each element of the m-dimensional vector p.sub.k constituting a member of the set P expresses a specific solution for a corresponding parameter in an optimal solution search problem being solved, and the vector p.sub.k corresponds to a specific solution vector. The elements p.sub.ki (i=1, . . . , m) of the vector p.sub.k may be referred to as genes and the vector p.sub.ki as a chromosome in association with a living creature. When using a genetic algorithm, first an initial set P of solution vectors is constructed appropriately.
&lt;&lt;Step 2&gt;&gt;
The goodness of the solution given by each member (chromosome) of the set P is evaluated using a predetermined evaluation criterion, and the result is presented as an evaluation value. Here, the predetermined evaluation criterion is called a fitness function.
&lt;&lt;Step 3&gt;&gt;
The fitness of the solution is judged on the basis of the magnitude of the evaluation value obtained in step 2. Depending on the problem, there are two cases: one in which a larger evaluation value means a higher fitness, and the other in which a smaller evaluation value means a higher fitness, the former being called the maximization problem and the latter the minimization problem. Solution vectors of low fitness are eliminated from the current solution set, and solution vectors of high fitness are selected for survival. This operation is called selection. Various methods are known for selection, but details of such methods should be referred to the above-mentioned document.
&lt;&lt;Step 4&gt;&gt;
Genetic recombination operations such as crossover and mutation are performed on the set of solution vectors selected in step 3, to construct a new solution vector set. It is assumed here that the number of individual solution vectors contained in the solution vector set is fixed, but it will be appreciated that the number may be increased or decreased. FIG. 71 illustrates the concept of recombination operations in the genetic algorithm, part (a) of the figure showing an example of the crossover operation and part (b) an example of the mutation operation.
Crossover is an operation for creating new solution vectors by replacing part of a solution vector expressed by a finite number of symbols with part of another vector, as shown in part (a). On the other hand, mutation is an operation by which part of the components of a solution vector selected from the solution vector set is changed, with a low probability, to another symbol, as shown in part (b). A crossover operation corresponds to a search at a position far apart from the current solution vector, while mutation corresponds to a search in the neighborhood of the current solution vector. With these two operations, the genetic algorithm construct a new set of solution vectors. Various methods have been proposed for the crossover, mutation, and other operations, but details of such methods should be referred to the above-mentioned document.
In the genetic algorithm, the above operations are iteratively performed until each solution vector in the solution vector set P converges to a nearly optimal solution to the problem being solved.
In the above-mentioned document, the "travelling salesman problem" is treated as an application example of optimization using the genetic algorithm. The names of N cities are denoted by 1 to N. Each member of the solution vector set P can be represented by a vector whose components are a permutation of 1 to N. The evaluation criterion is the total tour distance when the cities are visited in the order determined by the permutation. For example, when the cities are assigned A.sub.1, A.sub.2, . . . , A.sub.N and are visited in the order A.sub.1 .fwdarw.A.sub.2 .fwdarw. . . . .fwdarw.A.sub.N, the corresponding solution vector is (A.sub.1, A.sub.2, . . . , A.sub.N). This is simply denoted by A.sub.1 A.sub.2 A.sub.3 . . . A.sub.N, for example. By iteratively performing the above genetic algorithm thereafter, a travelling path nearly equal to the shortest path can be obtained.
FIG. 67 shows the configuration of a successive optimization processing apparatus based on the prior art genetic algorithm that is performed in accordance with the flowchart shown in FIG. 68. In FIG. 67, reference numeral 101 is an initial solution set setting section for setting an initial set of solution vectors to be improved; 102 is a genetic algorithm processing section for performing the estimation of an optimal solution vector by genetic operations; and 103 is an optimal solution output section for outputting a solution vector having the highest fitness when a predetermined termination condition is satisfied. The genetic algorithm processing section 102 comprises: an evaluation value acquisition section 104 for obtaining an evaluation value for each solution vector from a prescribed fitness function; a fitness calculation section 105 for calculating the fitness of each solution vector from the evaluation value obtained by the evaluation value acquisition section 104; a selection executing section 6701 for performing selection on the solution vector set in accordance with the fitness calculated by the fitness calculating section 105; a crossover operation executing section 202 for performing a crossover operation on solution vectors; and a mutation operation executing section 203 for performing a mutation operation on solution vectors. In the thus configured optimization adjusting apparatus using the prior art genetic algorithm, the process through the evaluation value acquisition section 104, the selection executing section 6701, the crossover operation executing section 202, and the mutation operation executing section 203 is performed iteratively in accordance with the flowchart shown in FIG. 68, successively updating the solution vector set and thereby estimating a nearly optimal solution vector for the optimization problem being solved.
However, for problems such as the adjustment of the characteristics of hearing aids, the creation of products and interior designs based on inexplicit concepts, and the adjustment of sound and image characteristics to match personal preferences, since the criteria used are idealistic and unclear and since the characteristics can vary greatly from one individual to another, there is the problem that the results of adjustments cannot be evaluated in quantitative terms. It is therefore not possible, in view of its principle, to apply to such problems a technique that, as in a neural network, predefines a clear fitness function and makes adjustments in such a manner as to optimize the fitness function. For example, the characteristics of a hearing aid are adjusted in the following procedure. First, a test sound signal is divided into several frequency ranges, and test signals are produced that correspond to the upper and lower limit levels of test sound in each frequency range. The upper and lower limit level test signals of the sound are input to the hearing aid, and the test signals output from the hearing aid are input to the ears of a hearing-impaired person, the user of the hearing aid, to confirm if the sound can be heard comfortably. If the lower limit level output test signal of the sound in a specific frequency range is too small and difficult to hear, a tuning specialist adjusts the frequency characteristics of the gain of the hearing aid so that the gain of the hearing aid is increased in that frequency range. Conversely, if the upper limit level output test signal of the sound in a specific frequency range is too large and is not pleasant to hear, the tuning specialist adjusts the frequency characteristics of the gain of the hearing aid so that the gain of the hearing aid is lowered in that frequency range. This process is repeated until the user is satisfied. Thus, under the current circumstances, a hearing aid tuning specialist adjusts the frequency characteristics of the gain of hearing aids, relying on his or her past experience, until the demand of the hearing-impaired user can be met; in fact, it takes a lot of time and labor to determine the characteristics that match each individual hearing-impaired person. Furthermore, the parameters for adjustment vary with the environment and with the personal preferences of each individual hearing-impaired person, and because of that, one hearing-impaired person has to have a plurality of hearing aids, the resulting problem being the need to adjust his or her hearing aids frequently. And each time such a need arises, he or she has to visit a tuning specialist who can adjust the characteristics of hearing aids.
Among the above-described genetic algorithm techniques, there has recently been proposed an interactive genetic algorithm by which the user evaluates each solution vector and, based on the evaluation value obtained, an optimal solution is estimated. Since evaluation and judgement can be made based only on human senses and the user's subjective evaluation, this interactive genetic algorithm can be applied to problems, such as those described earlier, for which a fitness function cannot be clearly prescribed. The prior art optimization adjusting methods for optimal solution vectors based on such an interactive genetic algorithm are disclosed, for example, in "Tracking a Criminal Suspect through "Face-Space" with a Genetic Algorithm" (Caldwell, C. and Johnston, V. S.: Proc. of 4th Int'l Conf. on Genetic Algorithms (ICGA '91)) and "Evolutionary Art and Computers" (Todd, S. and Latham, W.: Academic Press, Harcourt, Brace, Jovanovich).
An optimization adjusting method using an interactive genetic algorithm will be described briefly below.
FIG. 70 is a flowchart illustrating the principle of a solution vector optimization adjustment using an interactive genetic algorithm. As can be seen from the flowchart of FIG. 70, the significant difference from the previously described genetic algorithm is that in &lt;&lt;Step 2&gt;&gt; information such as an image or graphical figure expressed by each solution vector is presented for the user to evaluate the goodness of the solution vector, rather than providing an evaluation criterion predefined by an operation as in the previously described optimization adjusting method.
As an application example of optimal vector searching using the interactive genetic algorithm, the former document treats the application to "creation of a montage by a crime witness." The face is composed of such parts as hair, eyes, nose, mouth, chin, ears, etc. A plurality of pattern images are prepared for each part, and by combining pattern images of these parts, a face photograph is produced. Using the interactive genetic algorithm, a vector with the pattern number of each part as an element is defined as a solution vector. Then, the user, who is the witness, views a plurality of faces brought onto the display, each face being created by each solution vector, and subjectively judges the degree of resemblance to the suspect he or she witnessed. A photomontage that is considered most likely to express the face of the criminal suspect is thus produced by using the interactive genetic algorithm.
FIG. 69 shows the configuration of an optimization adjusting apparatus based on the prior art genetic algorithm that is performed in accordance with the flowchart of FIG. 70. In FIG. 69, the apparatus comprises an initial solution set setting section 101, an interactive genetic algorithm processing section 6901 for performing optimal vector searching by genetic recombination operations, and an optimal solution output section 103. The interactive genetic algorithm processing section 6901 includes an information presenting section 3207 for presenting information expressed by each solution vector to the user, a user evaluation judging section 3208 for making the user judge the evaluation value of each solution vector on the basis of the information presented by the information presenting section 3207, a fitness calculating section 105, and a recombination operation section 108. The information presenting section 3207 has the role of presenting information expressed by each solution vector to the user, and the user evaluation judging section 3208 makes the user evaluate the goodness of each solution vector on the basis of his or her own criteria and input his or her evaluation score. Otherwise, the configuration is fundamentally the same as that of the optimization adjusting apparatus using the genetic algorithm shown in FIG. 67, and further explanation is omitted here.
However, the genetic algorithm is a probabilistic and collective search method and uses information (evaluation value) only at the current point in the search space. Therefore, compared to a method wherein a search is made for solutions to a combinatorial optimization problem by using a neural network or the like that utilizes the curved surface features of a fitness function, the successive optimization processing apparatus using the prior art genetic algorithm is superior in global solution searching, but since local information is not used, it lacks the search ability in the neighborhood of an optimal solution and takes a longer time to search for solutions in that neighborhood. Furthermore, since the prior art does not use history information of past multi-point searches, there is a tendency to converge to the neighborhood of an optimal solution while more or less oscillating through the search space.
Furthermore, generally, in the optimization adjusting method based on the interactive genetic algorithm, it is necessary to evaluate the goodness of each solution vector by presenting multiple pieces of information expressed by each solution vector to the user for comparative evaluation. Therefore, the optimization adjusting apparatus using the prior art interactive genetic algorithm can be applied without any problem to the adjustment of static data such as characters and images that can be simultaneously presented spatially, but when the data to be evaluated by the user is time sequential information, such as the previously described problem of adjusting hearing aid characteristics, if multiple pieces of time sequential information are presented as they are, it is difficult for the user to distinguish the differences between them, so that it is extremely difficult to evaluate each solution vector. In addition, the burden on the user who is making the adjustment increases with time, and also, the user's preferences vary greatly. In reality, however, no measures to remedy these problems have ever been incorporated in the adjusting apparatus using the prior art interactive genetic algorithm.
The present invention is intended to resolve the above-outlined problems, and it is an object of the invention to provide an optimization adjusting apparatus capable of estimating an optimal solution quickly and effectively, by making improvements to the prior art genetic algorithm to reinforce its local search ability without impairing the global search ability innate to the genetic algorithm.
It is another object of the invention to provide an optimization adjusting apparatus that can effectively apply an interactive genetic algorithm not only to the adjustment of characters, images, etc., but to the adjustment of time sequential signals. It is a further object of the invention to provide an optimization adjusting method using an interactive genetic algorithm and an optimization adjusting apparatus implementing the same, which effectively alleviate the burden on a user who is working on the adjustment of an apparatus, by improving processing efficiency of solution vector optimization, and by modelling a user adjustment process from a user adjustment history and thereby automatically adjusting the solution vector.